package pers.whj.sort;

public class InsertSort<T> extends Sort<T> {
    public InsertSort(T[] data) throws SortException {
        super(data);
    }

    public InsertSort(T[] data, Compare<T> compare) throws SortException {
        super(data, compare);
    }

    @Override
    public void sort(int left, int right) throws SortException {
        sort(mData, mCompare, left, right);
    }

    public static <E> void sort(E[] data) throws SortException {
        sort(data, null);
    }

    public static <E> void sort(E[] data, Compare<E> compare) throws SortException {
        sort(data, compare, 0, data == null ? 0 : data.length - 1);
    }

    public static <E> void sort(E[] data, Compare<E> compare, int left, int right) throws SortException {
        check(data, compare, left, right);
        if (right - left >= 1) {
            for (int i = left + 1; i <= right; i++) {
                if (compare.swap(data[i - 1], data[i])) {
                    E temp = data[i];
                    int j = i - 1;
                    do {
                        data[j + 1] = data[j];
                        j--;
                    } while (j >= left && compare.swap(data[j], temp));
                    data[j + 1] = temp;
                }
            }
        }
    }
}